package com.atwulidun.recursion;

import java.util.*;

public class Maze {
    public static void main(String[] args) {
        // 一、首先获取迷宫行走策略全排列
        int[][] policyArrangement = getPolicyArrangement();
        // 二、获取最短路径对应的策略全排列数组的横坐标的队列
        Queue<Integer> index = getShortestWay(policyArrangement);
        // 三、根据最短路径对应的策略全排列数组的横坐标的队列打印出相应的迷宫
        printMaze(policyArrangement, index);
    }

    // 初始化迷宫的方法("0"表示未走过，"1"表示墙，"2"表示能走得通，"3"表示走不通)
    public static int[][] initializeMaze() {
        // 首先创建一个二维数组
        int[][] maze = new int[8][7];
        // 设置墙
        // 对第一行和最后一行进行设置
        for (int i = 0; i < 7; i++) {
            maze[0][i] = 1;
            maze[7][i] = 1;
        }
        // 对第一列和最后一列进行设置
        for (int i = 1; i < 7; i++) {
            maze[i][0] = 1;
            maze[i][6] = 1;
        }
        // 对挡板进行设置
        maze[3][1] = 1;
        maze[3][2] = 1;
        return maze;
    }

    // 统计迷宫里数字"2"个数的方法
    public static int count2(int[][] maze) {
        int count = 0;
        for (int[] ints : maze) {
            for (int anInt : ints) {
                if (anInt == 2) {
                    count++;
                }
            }
        }
        return count;
    }

    // 根据policyFullArrangement里面的具体某一种策略来打印迷宫的方法，index保存着最短路径对应的policyFullArrangement的横坐标
    public static void printMaze(int[][] policyFullArrangement, Queue<Integer> index) {
        int[][] maze = initializeMaze();
        int[][] direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};// 分别对应上右下左
        int[][] policy = new int[4][2];
        while (!index.isEmpty()) {
            int j = index.poll();// 特别小心poll()方法，每调用一次队列的长度都会发生变化，因此只能够poll()一次
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < 4; i++) {
                policy[i][0] = direction[policyFullArrangement[j][i]][0];
                policy[i][1] = direction[policyFullArrangement[j][i]][1];
                switch (policyFullArrangement[j][i]) {
                    case 0:
                        stringBuilder.append("上");
                        break;
                    case 1:
                        stringBuilder.append("右");
                        break;
                    case 2:
                        stringBuilder.append("下");
                        break;
                    case 3:
                        stringBuilder.append("左");
                        break;
                }
            }
            setWay(maze, 1, 1, policy);// 按照具体的某个策略来走迷宫
            System.out.println("本次走迷宫的策略是： " + stringBuilder.toString());
            System.out.println("本次走迷宫路径长为： " + count2(maze));
            System.out.println("本次走迷宫路径图为：");
            // 把按照上面策略走完的迷宫打印出来
            for (int[] ints : maze) {
                for (int anInt : ints) {
                    System.out.print(anInt + " ");
                }
                System.out.println();
            }
            System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
            // 记得对迷宫重新初始化以备下一次while循环
            maze = initializeMaze();
        }
    }

    // 获取迷宫行走策略全排列的方法(上下左右的全排列，一共有24中策略)
    public static int[][] getPolicyArrangement() {
        int[] arr = {0, 1, 2, 3};// 注意：这里存放的是数组的下标，写成{1, 2, 3, 4}数组就越界啦！！！！！！！！！！！！！！
        int[][] policyArrangement = new int[24][4];
        int[] iArray = {0};
        fullArrangement(arr, 0, policyArrangement, iArray);
        return policyArrangement;
    }

    // 通用获取全排列的方法

    /**
     * @param arr               保存全排列的数字
     * @param start             从arr的第start位开始全排列
     * @param policyArrangement 保存全排列
     * @param iArray            对policyArrangement的行数进行自增
     */
    public static void fullArrangement(int[] arr, int start, int[][] policyArrangement, int[] iArray) {
        if (start == arr.length) {
            int i = iArray[0];
            System.arraycopy(arr, 0, policyArrangement[i], 0, 4);
            iArray[0] = ++i;
            return;
        }
        for (int j = start; j < arr.length; j++) {
            swap(arr, start, j);
            fullArrangement(arr, start + 1, policyArrangement, iArray);
            swap(arr, start, j);
        }
    }

    // 对数组里元素进行交换的方法
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 判断路径是否行得通的方法
    public static boolean setWay(int[][] maze, int i, int j, int[][] policy) {
        if (maze[6][5] == 2) {
            return true;
        } else {
            // 如果当前的坐标没有走过
            if (maze[i][j] == 0) {
                // 先假设当前的路是通的，若真的是通的，就保留当前位置的2，若不通则后面再将其改为3
                maze[i][j] = 2;
                if (setWay(maze, i + policy[0][0], j + policy[0][1], policy)) {
                    return true;
                } else if (setWay(maze, i + policy[1][0], j + policy[1][1], policy)) {
                    return true;
                } else if (setWay(maze, i + policy[2][0], j + policy[2][1], policy)) {
                    return true;
                } else if (setWay(maze, i + policy[3][0], j + policy[3][1], policy)) {
                    return true;
                } else {
                    // 若四个方向都走不通，则将maze[i][j]重置为3
                    maze[i][j] = 3;
                    return false;
                }
            } else {
                // 如果当前坐标的值为1，2，3，则直接返回false即可
                return false;
            }
        }
    }

    // 获取最短路径的方法(返回最短路径对应的policyFullArrangement的横坐标组成的list)
    public static Queue<Integer> getShortestWay(int[][] policyFullArrangement) {
        int[][] maze = initializeMaze();
        int[][] direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        int[][] policy = new int[4][2];
        Queue<Integer> index = new LinkedList<>();
        int minCount = 57;// 迷宫一共56个格子，所以2的最大数量一定小于57，这是为了把第一种策略的2的数量赋值给minCount，不破坏代码的结构
        int minI;// 与minCount对应的i的值
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < 24; i++) {
            for (int j = 0; j < 4; j++) {
                policy[j][0] = direction[policyFullArrangement[i][j]][0];
                policy[j][1] = direction[policyFullArrangement[i][j]][1];
            }
            setWay(maze, 1, 1, policy);// 按照具体的某个策略来走迷宫(注意：是从坐标(1,1)开始而不是(0,0)开始！！！！！！！！！！！！)
            // 统计出按该种策略走完迷宫后迷宫里2的数量
            int count2 = count2(maze);
            if (count2 <= minCount) {
                minCount = count2;
                minI = i;
                map.put(minI, minCount);// 因为minCount可以有相同值，而minI都是不同的，所以后者为key，前者为value
            }
            // 记得把迷宫重置以便下一次for循环使用
            maze = initializeMaze();
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer mapKey = entry.getKey();
            Integer mapValue = entry.getValue();
            if (mapValue == minCount) {
                index.add(mapKey);
            }
        }
        return index;
    }
    // 总结遇到的问题(全是数组的下标问题)：
    // 1.int[] arr = {0, 1, 2, 3};// 注意：这里存放的是数组的下标，写成{1, 2, 3, 4}数组就越界啦！！！！！！！！！！！！！！
    // 2.policy的横坐标要记得变化啊，不要直接复制粘贴就不管了
    // if (setWay(maze, i + policy[0][0], j + policy[0][1], policy)) {
    //                    return true;
    //                } else if (setWay(maze, i + policy[1][0], j + policy[1][1], policy)) {
    //                    return true;
    //                } else if (setWay(maze, i + policy[2][0], j + policy[2][1], policy)) {
    //                    return true;
    //                } else if (setWay(maze, i + policy[3][0], j + policy[3][1], policy)) {
    //                    return true;
    //                }
    // 3.setWay(maze, 1, 1, policy);// 注意：是从坐标(1,1)开始而不是(0,0)开始！！！！！！！！！！！！
}
